package leetcode;

import java.util.*;
import java.util.LinkedList;
import java.util.Queue;

class RecentCounter {
    int count;
    Queue<Integer> queue=null;
    public RecentCounter() {
        queue=new LinkedList<>();
        count=0;
    }
    public int ping(int t) {
        queue.add(t);
        for (int num:queue) {
            if (num>=(t-3000)&&num<=t){
                count++;
            }
        }
        int sum=count;
        count=0;
        return sum;
    }
}

public class LeetCodeMain121 {
    public boolean isPalindrome(ListNode head) {
        if (head==null||head.next==null){
            return true;
        }
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode n1=slow;
        ListNode n2=slow.next;
        ListNode n3=n2.next;
        while (n3!=null){
            n2.next=n1;
            n1=n2;
            n2=n3;
            n3=n3.next;
        }
        while (head!=n2){
            if (head.val!=n2.val){
                return false;
            }
            head=head.next;
            n2=n2.next;
        }
        return true;
    }
    List<Integer> list=new ArrayList<>();
    Set<Integer> set=new HashSet<>();
    public boolean findTarget(TreeNode root, int k) {
        if (root==null){
            return false;
        }
        if (set.contains(k-root.val)){
            return true;
        }
        set.add(root.val);
        return findTarget(root.left, k)||findTarget(root.right, k);
    }
    public boolean findTarget1(TreeNode root, int k) {
        if (root==null){
            return false;
        }
        preOrder(root);
        for (int num:list) {
            if (set.contains(k-num)&&num*2!=k){
                return true;
            }
        }
        return false;
    }
    public void preOrder(TreeNode root){
        if (root==null){
            return;
        }
        list.add(root.val);
        set.add(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }
    public int mySqrt(int x) {
//        return (int)Math.sqrt(x);
        int l=0,r=x,res=-1;
        while (l<=r){
            int mid=(l+r)/2;
            if ((long)mid*mid<=x){
                l=mid+1;
                res=mid;
            }else {
                r=mid-1;
            }
        }
        return res;
    }
    public boolean isAlienSorted(String[] words, String order) {
        for (int i = 1; i < words.length; i++) {
            boolean flag=false;
            for (int j = 0; j < words[i-1].length()&&j<words[i].length(); j++) {
                int pre=order.indexOf(words[i-1].charAt(j));
                int end=order.indexOf(words[i].charAt(j));
                if (pre>end){
                    return false;
                }else if (pre<end){
                    flag=true;
                    break;
                }
            }
            if (!flag){
                if (words[i - 1].length() > words[i].length()) {
                    return false;
                }
            }
        }
        return true;
    }
}
